package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.TreeNode;
import javafx.util.Pair;

public class Day32 {


    /***
     * 是否是平衡二叉树
     * @return
     */
    public static boolean isAVL(TreeNode root) {
        return process(root).getKey();
    }

    public static Pair<Boolean, Integer> process(TreeNode root) {
        //当前节点为null 那么是平衡二叉树
        if (root == null) {
            return new Pair<>(true, 0);
        }
        //右树
        Pair<Boolean, Integer> rightData = process(root.right);
        //左树
        Pair<Boolean, Integer> leftData = process(root.left);
        //右树是否是平衡
        boolean rTreeIsAVL = rightData.getKey();
        //右树高度
        int rHigh = rightData.getValue();
        //左树是否平衡
        boolean lTreeIsAVL = leftData.getKey();
        //左树高度
        int lHigh = rightData.getValue();
        //当前树是平衡要求：左树平衡 右树平衡 且二者高度差小于1
        boolean thisNodeIsAvl = rTreeIsAVL
                && lTreeIsAVL
                && Math.abs(rHigh - lHigh) < 2;
        //返回当前树的结果 高度树是左右高度最大+1
        return new Pair<>(thisNodeIsAvl, Math.max(rHigh, lHigh) + 1);
    }

}
